package demo.practice.trie;

import java.util.*;

public class P1707_2 {


    public static void main(String[] args) {

        /**
         * [513348508,439134316,535667100,536280044,330170208]
         * [1050219420,844498962,540190212,539622516,330170208]
         */
        P1707_2 p1707_2 = new P1707_2();
        int[] ints = p1707_2.maximizeXor(new int[]{536870912, 0, 534710168, 330218644, 142254206}, new int[][]{{558240772, 1000000000},
                {307628050, 1000000000}, {3319300, 1000000000}, {2751604, 683297522}, {214004, 404207941}});
        System.out.println(Arrays.toString(ints));
    }


    public int[] maximizeXor(int[] nums, int[][] queries) {


        int[] res = new int[queries.length];
        Arrays.sort(nums);
        int[][] qmk = new int[queries.length][3];
        for (int i = 0; i < queries.length; i++) {
            qmk[i][0] = queries[i][0];
            qmk[i][1] = queries[i][1];
            qmk[i][2] = i;
        }

        Arrays.sort(qmk, (o1, o2) -> o1[1] - o2[1]);


        int nindex = 0;
        Trie t = new Trie();
        for (int[] query : qmk) {
            int v = query[0];
            int m = query[1];

            if (m < nums[0]) {
                res[query[2]] = -1;
            } else {
                while (nindex < nums.length && nums[nindex] <= m) {
                    t.insert(nums[nindex++]);
                }
                res[query[2]] = t.maxXOR(v);
            }
        }

        return res;
    }


    class Trie {
        //Map<Integer, Trie> child = new HashMap<>();
//        int child_count = 0;

        Trie[] child = new Trie[2];
        //List<Integer> list = new ArrayList<>();
        //PriorityQueue<Integer> queue = new PriorityQueue<Integer>(Integer::compareTo);

        public void insert(int num) {
            //queue.add(num);
            Trie cur = this;
            for (int i = 30; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if (cur.child[bit] == null) {
                    cur.child[bit] = new Trie();
                    cur = cur.child[bit];
                    //cur.child_count++;  //当前分支有几个子节点
                } else {
                    cur = cur.child[bit];
                    //cur.child_count++;  //当前分支有几个子节点
                }
            }
        }

        /*public void remove(int num) {
            Trie cur = this;
            for (int i = 30; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if (cur.child[bit] == null) {
                    return;
                } else {
                    cur.child[bit].child_count--;
                    if (cur.child[bit].child_count == 0) {
                        cur.child[bit] = null;
                        return;
                    } else {
                        cur = cur.child[bit];
                    }
                }
            }
        }*/

        public int maxXOR(int query) {
            Trie cur = this;
            int res = 0;
            for (int i = 30; i >= 0; i--) {
                int bit = (query >> i) & 1;

                if (bit == 0) {
                    if (cur.child[1] != null) {
                        //这一位有值
                        res = res | (1 << i);
                        cur = cur.child[1];
                    } else {
                        cur = cur.child[0];
                    }
                } else {
                    if (cur.child[0] != null) {
                        //这一位有值
                        res = res | (1 << i);
                        cur = cur.child[0];
                    } else {
                        cur = cur.child[1];
                    }
                }
            }
            return res;
        }
    }
}
